package problems.solved;

import java.util.HashMap;
import java.util.Map;

import problems.Problem;

public class Problem15 extends Problem<Long> {
	private static final Map<Point, Long> cache = new HashMap<Point, Long>();
	
	public static void main(String[] args) {
		Problem15 problem15 = new Problem15();
		problem15.runTimed();
		problem15.printResult();
	}

	@Override
	public void run() {
		setResult(routes(new Point(20,20)));
	}

	private static long routes(Point p) {
		if (p.down == 1){ 
			return p.right + 1;
		}
		if (p.right == 1) {
			return p.down + 1;
		}
		if (cache.containsKey(p)) {
			return cache.get(p);
		}
		final long val = routes(p.down()) + routes(p.right());
		cache.put(p, val);
		return val;
	}
	
	private static class Point {
		private final int right;
		private final int down;

		public Point(int a, int b) {
			this.right = a;
			this.down = b;
		}
		
		@Override
		public boolean equals(Object obj) {
			if (obj instanceof Point) {
				Point p = (Point)obj;
				return (p.right == right && p.down == down) || (p.down == right && p.right == down);
			}
			return false;
		}
		
		@Override
		public int hashCode() {
			return 31*(right+down);
		}
		
		@Override
		public String toString() {
			return String.format("[%d, %d]", right, down);
		}
		
		public Point down() {
			return new Point(right, down-1);
		}
		
		public Point right() {
			return new Point(right-1, down);
		}
	}
}
